Online maps provide advertising opportunities for businesses represented on the maps. Visual advertisements may be included in online maps for display to end users. Including a visual advertisement of a business on an online map is beneficial compared to simply including a textual label for the business because the advertisement creates a branding effect that users associate with the business. However, because screen real-estate in online maps is limited, simply displaying advertisements for all businesses represented on the online maps may degrade the usefulness of online maps by cluttering the maps with excess information.